In recent years, in accordance with the advance of digital signal processing technology, a large amount of digital information such as moving images, still images and audio information can be encoded with high efficiency, and can be recorded on a small recording medium or transmitted via a communication medium. A video encoding apparatus is developed utilizing this technique for converting TV-broadcasted video images or video images obtained with a video camera into stream data. Among the moving image coding methods, ITU-T H.264 standard (MPEG 4 part 10/AVC) has attracted particular attention. Entropy coding is the main technique behind many recent high-efficiency compression encoding and arithmetic coding is known as a particularly highly-efficient entropy coding. Arithmetic coding is adopted in the aforementioned H.264 standard.
In the H.264 standard, arithmetic coding known as Context-based Adaptive Binary Arithmetic Coding (hereinbelow, abbreviated to “CABAC”) and variable-length coding known as Context-based Adaptive Variable length coding (hereinbelow, abbreviated to “CAVLC”) are employed.
As a related art, Japanese Patent Laid-Open No. 2004-135251 proposes a technique focused on the abovementioned CABAC and CAVLC. The application discloses “image information coding method and image information decoding method” of limiting the amount of input/output data to CABAC thereby ensuring processing time in a decoder.
FIG. 5 is a flowchart showing a processing procedure of a conventional arithmetic coding method.
Note that this processing procedure is defined with the ITU-T H.264 standard and is publicly known. The H.264 arithmetic coding, i,e, CABAC coding, handles input of a binary symbol.
In FIG. 5, at step S900, it is determined whether or not the input of a symbol has been completed. When it is determined that the input has not been completed (No at step S900), a symbol is inputted at step S901. The input symbol is “0” or “1”, a binary symbol. Next, at step S902, zone dividing is performed. The zone means an area of integers from “0” to “1023” represented with a lower limit and a length. The zone dividing refers to dividing a zone into two zones at a ratio between occurrence probabilities of the binary symbols. For example, when the occurrence probability of symbol “0” is 75% and that of symbol “1” is 25%, the zone is divided at a ratio of 75 to 25 (in this case, the symbol “0” is referred to as an “MPS (More Probable Symbol)”, the symbol “1”, as an “LPS (Less Probable Symbol)”. Next, at step S903, one of the divided zones is selected in accordance with the input symbol.
FIG. 6 shows an example where the current zone is represented with a lower limit value “21” and a length “320”. The occurrence probabilities of the symbols 0 and 1 are 75% and 25%. When an input symbol is “1”, the “1” zone is selected. As a result, the new lower limit is “261” and the length is “80”.
Next, at step S904, it is determined whether or not the length of the new zone is less than “256”. When the length of the zone is greater than or equal to “256” (NO at step S904), the process returns to step S900. Further, as in the case of FIG. 6, when the length of the zone is “80” and is less than “256” (YES at step S904), the process branches to step S905.
At step S905, it is determined whether or not the value of the lower limit of the zone is less than “256”. When the lower limit of the zone is less than “256” (YES at step S905), the process branches to step S906, at which “0” is outputted as a code stream. At step S907, “1” is outputted in correspondence with the number of reserved bits to be described later, as a code stream. Further, the number of reserved bits is reset to zero. At step S908, the zone is normalized. The normalization is processing to expand the length of a zone less than “256” and ensure precision in the subsequent processing. At step S908, the value of the lower limit and the length of the zone are doubled.
At step S905, when it is determined that the lower limit is greater than or equal to “256” (NO at step S905), the process branches to step S909, at which it is determined whether or not the lower limit of the zone is less than “512”. If it is determined that the lower limit of the zone is less than “512” (YES at step S909), the process branches to step S910. If it is determined that the lower limit of the zone is greater than or equal to “512” (NO at step S909), the process branches to step S912.
At step S912, “1” is outputted as a code stream, and at step S913, “0” is outputted in correspondence with the number of reserved bits to be described later, as a code stream. The number of reserved bits is reset to zero. At step S914, the zone is normalized. In the normalization at this step, a value, obtained by subtracting “512” from the value of the lower limit and doubling the subtraction result, is set as a new value of the lower limit. Further, the length of the zone is doubled.
Further, at step S909, when it is determined that the value of the lower limit is less than “512”, the process branches to step S910, at which the number of reserved bits is incremented by one. Next, at step S911, the zone is normalized. In the normalization at step S911, “256” is subtracted from the value of the lower limit, then the subtraction result is doubled, and the length of the zone is doubled. In the example of FIG. 6, the value of the lower limit becomes “10” (=(261−256)×2), and the length of the zone becomes “160” (=80×2). Further, the number of reserved bits is incremented to “1”. After these normalization processing steps, the process returns to step S904, to repeat the normalization processing until the length of the zone becomes greater than or equal to “256”.
For example, in FIG. 6, as the length of the normalized zone is “160”, the process proceeds from step S904 to step S905 again. As the value of the lower limit is “10”, the process proceeds to step S906. At step S906, “0” is outputted, and as the number of reserved bits has been incremented to “1”, one “1” is outputted (step S907). That is, a code stream “01” is outputted. Further, by the normalization processing at step S908, the value of the lower limit is doubled to “20” and the length of the zone is doubled to “320”. As the length of the zone is greater than “256”, the process returns from step S904 to step S900. The above processing is repeated until the completion of input is detected at step S900 and the process branches to termination processing at step S915.
In the consideration of the inventor, the above-described conventional arithmetic coding has two problems. The first problem is the large number of steps to process one input symbol in the loop from step S904 to step S914, which may increase software processing time or increase the hardware circuit scale. The second problem is the increase in memory capacity for holding values in repetition of increment of the number of reserved bits at step S910, and by extension, the increase in the amount of processing time at steps S907 and S913 as reserved bit resolving processing.